/*
 * Hash.hpp
 * Author: Elias Capito, Yanick Candaux
 * PCM
 */


#ifndef HASH_HPP_
#define HASH_HPP_

#include "HashNode.hpp"
#include "HazardQueue.hpp"
#include <cstdlib>
#include <cstring>
#include <iostream>
#include "def.hpp"
using namespace std;
namespace pcm {

typedef union{
	HashNode*node;
	LL value;
} HashNodeConversion;


class Hash {
public:
	Hash();
	virtual ~Hash();

	HashNode*** m_primaryBuckets;
	int m_itemCount;
	int m_size;


	inline void clear(){
		HashNode* hn = m_primaryBuckets[0][0];
		while(true){
			if(hn==NULL){
				break;
			}else
			{
				HashNode* tmp = hn;
				hn = hn->m_next;
				delete tmp;
			}

		}
		deleteBuckets();
	}

	inline void deleteBuckets(){
		for(int i=0;i<48;i++){
			if(m_primaryBuckets[i]!=NULL)
			delete[] m_primaryBuckets[i];
		}
		delete[] m_primaryBuckets;
	}

	/**
	 * crée table primaire, table secondaire et la sentinelle 0. Doit être appelée avant toute autre fonction
	 * agissant sur la table
	 * @return true si pas de problème de malloc, false autrement
	 */
	inline bool initialize(){
		m_primaryBuckets = new HashNode**[48];
		for(int i=0;i<48;i++){
			m_primaryBuckets[i] = NULL;
		}
		if(m_primaryBuckets!=NULL){
			m_primaryBuckets[0] = new HashNode*[m_size];
			for(int i=0;i<m_size;i++){
				m_primaryBuckets[0][i] = NULL;
			}
			if(m_primaryBuckets[0]!=NULL){
				m_primaryBuckets[0][0] = new HashNode();
				if(m_primaryBuckets[0][0]!=NULL){
					m_primaryBuckets[0][0]->m_sentinel = true;
					m_primaryBuckets[0][0]->m_next = NULL;
					m_primaryBuckets[0][0]->m_reversedKey=0;
					m_primaryBuckets[0][0]->m_item = NULL;

					return true;
				}
				delete[] m_primaryBuckets[0];
			}
			delete[] m_primaryBuckets;
		}
		return false;
	}

	/**
	 * Crée une sentinelle et l'insère dans la liste. C'est ensuite à l'appelant d'insérer la sentinelle dans
	 * la table secondaire
	 * @return Noeud sentinelle crée
	 */
	inline HashNode* initializeBucket(LL _key){
		HashNode *sentinel, *parentBucket, *pred;
		LL parent = m_size;
		while((parent = parent>>1)> _key);
		parentBucket = getSecondaryBucket(_key-parent);
		if((sentinel = new HashNode()) != NULL){
			sentinel->m_sentinel = true;
			sentinel->m_item = NULL;
			sentinel->m_reversedKey = _key = BoardInfos::reverseAllBoard(_key);
			sentinel->m_next = NULL;
			if(!listInsert(parentBucket,sentinel)) {
				delete sentinel;
				if(!find(parentBucket,_key,true,&pred,&sentinel)){
					return NULL;
				}
			}
		}
		return sentinel;
	}

	/**
	 * Retourne la sentinelle ou débute toutes les opérations Add, Contains, Remove
	 */
	inline HashNode* getSecondaryBucket(LL _key){
		LL i,min,max;
		HashNode **secondary,*sentinel;
		for(i=min=0,max=2;_key>=max;i+=1,max<<=1){
			min=max;
		}
		if(m_primaryBuckets[i]==NULL){
			int size = m_size>>1;
			secondary = new HashNode*[size];//(HashNode**)calloc(m_size>>1,sizeof(HashNode*));
			for(int k = 0;k<size;k++){
				secondary[k] = NULL;
			}
			if(secondary==NULL){
				return NULL;
			}
			if(!bcasptr(&m_primaryBuckets[i],NULL,secondary)){
				delete secondary;
			}
		}
		if(m_primaryBuckets[i][_key-min]==NULL){
			if((sentinel=initializeBucket(_key))!=NULL){
				m_primaryBuckets[i][_key-min] = sentinel;
			}
		}
		return m_primaryBuckets[i][_key-min];
	}

	/**
	 * Add or increment number join
	 * @param item
	 * @param boardToProcess
	 * @param reuseBoard
	 * @param iThread
	 * @return
	 */
	inline bool specificAddOrIncrement(BoardInfos* item,HazardQueue * boardToProcess,HazardQueue * reuseBoard, int iThread){
		HashNode* bucket,*newNode;
		LL size, key;
		if((newNode= new HashNode())==NULL){
			return false;
		}

		newNode->m_sentinel=false;
		key= item->board();
		newNode->m_reversedKey = BoardInfos::reverseAllBoard(key);
		newNode->m_item = item;
		if((bucket=getSecondaryBucket(key%m_size))==NULL){
			return false;
		}

		HashNode *p, *c;
		while(true){
			if(find(bucket,newNode->m_reversedKey,newNode->m_sentinel,&p,&c)){
				c->m_item->incrementNumberJoin(item->numberJoin());
				reuseBoard->enq(item,0);
				delete newNode;
				return true;
			}
			newNode->m_next=c;
			if(bcasptr(&p->m_next,c,newNode)){
				boardToProcess->enq(item,iThread);
				size = m_size;
				if(AtomicFetchAndIncrement(&m_itemCount,1)/size>=MAXLOAD){
					cas64(&m_size,size,size*2);
				}

				return true;
			}
		}

	}

	/**
	 * Insert un noeud dans la liste à partir de la sentinelle head
	 * @return true si le noeud a été inséré et false s'il s'agit d'un doublon
	 */
	inline bool listInsert(HashNode *_head,HashNode *_node){
		HashNode *p, *c;
		while(true){
			if(find(_head,_node->m_reversedKey,_node->m_sentinel,&p,&c)){
				return false;
			}
			_node->m_next=c;
			if(bcasptr(&p->m_next,c,_node)){
				return true;
			}
		}
	}

	/**
	 * Parcourt la liste depuis la sentinelle head à la recherche des noeuds précédent(pred) et suivant(curr) à
	 * celui recherché et qui est identifié par sa clé inverse(rKey)
	 * @return true si la clé est déjà contenue dans la liste, curr dans ce cas désigne le noeud recherché;
	 * false si la clé n'est pas contenue dans la liste, dans ce cas pred et curr désignent les noeuds ou
	 * il peut y avoir une insertion
	 */
	inline bool find(HashNode *head, LL rKey,bool isSent,HashNode**pred,HashNode**curr){
		HashNodeConversion next;
		while(true) {
			*pred = head;
			*curr=(*pred)->m_next;
			while(true){
				if(*curr==NULL){
					return false;
				}
				next.node = (*curr)->m_next;
				if(next.value&0x1){
					next.value ^= 0x1;
					if(casptr(&(*pred)->m_next,*curr,next.node)){
						*curr = next.node;
					}else{
						break;
					}
				}else if((*curr)->m_reversedKey==rKey && isSent == (*curr)->m_sentinel){
					return true;
				}else if((*curr)->m_reversedKey==rKey &&isSent){
					return false;
				}else if((*curr)->m_reversedKey>rKey){
					return false;
				}else{
					*pred = *curr;
					*curr = next.node;
				}
			}
		}
		return false;
	}

	/**
	 * Add item to hash
	 */
	inline bool add(BoardInfos* item){
		HashNode* bucket,*newNode;
		LL size, key;
		if((newNode= new HashNode())==NULL){
			return false;
		}

		newNode->m_sentinel=false;
		key= item->board();
		newNode->m_reversedKey = BoardInfos::reverseAllBoard(key);
		newNode->m_item = item;
		if((bucket=getSecondaryBucket(key%m_size))==NULL){
			return false;
		}
		if(!listInsert(bucket,newNode)){
			delete newNode;
			return false;
		}
		size = m_size;
		if(AtomicFetchAndIncrement(&m_itemCount,1)/size>=MAXLOAD){
			cas64(&m_size,size,size*2);
		}
		return true;
	}
	/**
	 * Remove item in hash
	 * @param item
	 * @return
	 */
	inline bool remove(BoardInfos* item){
		HashNode* pred, *curr, *bucket, *tmpNext;
		HashNodeConversion next;
		LL key = item->board();
		if((bucket = getSecondaryBucket(key%m_size))==NULL){
			return false;
		}
		key = BoardInfos::reverseAllBoard(key);
		while(true){
			if(!find(bucket,key,false,&pred,&curr)){
				return false;
			}
			next.node = tmpNext = curr->m_next;
			if((next.value &0x1)== 0){
				next.value |= 0x1;
				if(bcasptr(&curr->m_next,tmpNext,next.node)){
					casptr(&pred->m_next,curr,tmpNext);

					curr->m_next=NULL;
					curr->m_item=NULL;
					delete curr;
					curr = NULL;
					AtomicFetchAndDecrement(&m_itemCount,1);
					return true;
				}
			}
		}
		return false;
	}
};

} /* namespace pcm */
#endif /* HASH_HPP_ */
